      1  import java.util.*;

      2

      3  /**

      4     This class implements a heap.

      5  */

      6  public class MinHeap

      7  {

      8     private ArrayList<Comparable> elements;

      9

     10     /**

     11        Constructs an empty heap.

     12     */

     13     public MinHeap()

     14     {

     15        elements = new ArrayList<Comparable>();

     16        elements.add(null);

     17     }

     18

     19     /**

     20        Adds a new element to this heap.

     21        @param newElement the element to add

     22     */

     23     public void add(Comparable newElement)

     24     {

     25        // Add a new leaf

     26        elements.add(null);

     27        int index = elements.size() - 1;

     28

     29        // Demote parents that are larger than the new element

     30        while (index > 1

     31              && getParent(index).compareTo(newElement) > 0)

     32        {

     33           elements.set(index, getParent(index));

     34           index = getParentIndex(index);

     35        }

     36

     37        // Store the new element into the vacant slot

     38        elements.set(index, newElement);

     39     }

     40

     41     /**

     42        Gets the minimum element stored in this heap.

     43        @return the minimum element

     44     */

     45     public Comparable peek()

     46     {

     47        return elements.get(1);

     48     }

     49

     50     /**

     51        Removes the minimum element from this heap.

     52        @return the minimum element

     53     */

     54     public Comparable remove()

     55     {

     56        Comparable minimum = elements.get(1);

     57

     58        // Remove last element

     59        int lastIndex = elements.size() - 1;

     60        Comparable last = elements.remove(lastIndex);

     61

     62        if (lastIndex > 1)

     63        {

     64           elements.set(1, last);

     65           fixHeap();

     66        }

     67

     68        return minimum;

     69     }

     70

     71     /**

     72        Turns the tree back into a heap, provided only the root

     73        node violates the heap condition.

     74     */

     75     private void fixHeap()

     76     {

     77        Comparable root = elements.get(1);

     78

     79        int lastIndex = elements.size() - 1;

     80        // Promote children of removed root while they are smaller than last

     81

     82        int index = 1;

     83        boolean more = true;

     84        while (more)

     85        {

     86           int childIndex = getLeftChildIndex(index);

     87           if (childIndex <= lastIndex)

     88           {

     89              // Get smaller child

     90

     91              // Get left child first

     92              Comparable child = getLeftChild(index);

     93

     94              // Use right child instead if it is smaller

     95              if (getRightChildIndex(index) <= lastIndex

     96                    && getRightChild(index).compareTo(child) < 0)

     97              {

     98                 childIndex = getRightChildIndex(index);

     99                 child = getRightChild(index);

    100              }

    101

    102              // Check if larger child is smaller than root

    103              if (child.compareTo(root) < 0)

    104              {

    105                 // Promote child

    106                 elements.set(index, child);

    107                 index = childIndex;

    108              }

    109              else

    110              {

    111                 // Root is smaller than both children

    112                 more = false;

    113              }

    114           }

    115           else

    116           {

    117              // No children

    118              more = false;

    119           }

    120        }

    121

    122        // Store root element in vacant slot

    123        elements.set(index, root);

    124     }

    125

    126     /**

    127        Checks whether this heap is empty.

    128     */

    129     public boolean empty()

    130     {

    131        return elements.size() == 1;

    132     }

    133

    134     /**

    135        Returns the index of the left child.

    136        @param index the index of a node in this heap

    137        @return the index of the left child of the given node

    138     */

    139     private static int getLeftChildIndex(int index)

    140     {

    141        return 2 * index;

    142     }

    143

    144     /**

    145        Returns the index of the right child.

    146        @param index the index of a node in this heap

    147        @return the index of the right child of the given node

    148     */

    149     private static int getRightChildIndex(int index)

    150     {

    151        return 2 * index + 1;

    152     }

    153

    154     /**

    155        Returns the index of the parent.

    156        @param index the index of a node in this heap

    157        @return the index of the parent of the given node

    158     */

    159     private static int getParentIndex(int index)

    160     {

    161        return index / 2;

    162     }

    163

    164     /**

    165        Returns the value of the left child.

    166        @param index the index of a node in this heap

    167        @return the value of the left child of the given node

    168     */

    169     private Comparable getLeftChild(int index)

    170     {

    171        return elements.get(2 * index);

    172     }

    173

    174     /**

    175        Returns the value of the right child.

    176        @param index the index of a node in this heap

    177        @return the value of the right child of the given node

    178     */

    179     private Comparable getRightChild(int index)

    180     {

    181        return elements.get(2 * index + 1);

    182     }

    183

    184     /**

    185        Returns the value of the parent.

    186        @param index the index of a node in this heap

    187        @return the value of the parent of the given node

    188     */

    189     private Comparable getParent(int index)

    190     {

    191        return elements.get(index / 2);

    192     }

    193  }